<!DOCTYPE html>
<!--[if lt IE 7 ]><html class="ie ie6" lang="en"> <![endif]-->
<!--[if IE 7 ]><html class="ie ie7" lang="en"> <![endif]-->
<!--[if IE 8 ]><html class="ie ie8" lang="en"> <![endif]-->
<!--[if (gte IE 9)|!(IE)]><!-->
<html lang="en">
<!--<![endif]-->

<head>

    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="description" content="">
    <meta name="author" content="">
    <meta name="keywords" content="">

    <title>Process Scheduling Algorithms</title>

    {% load static %}
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/fonts/font-awesome-4.3.0/css/font-awesome.min.css' %}">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/css/stroke.css' %}">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/css/bootstrap.css' %}">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/css/animate.css' %}">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/css/prettyPhoto.css' %}">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/css/style.css' %}">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/js/syntax-highlighter/styles/shCore.css' %}" media="all">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/js/syntax-highlighter/styles/shThemeRDark.css' %}" media="all">
    <link rel="stylesheet" type="text/css" href="{%static 'wikipages/css/custom.css' %}">

    <!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
    <!--[if lt IE 9]>
      <script src="https://oss.maxcdn.com/html5shiv/3.7.2/html5shiv.min.js"></script>
      <script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
    <![endif]-->

</head>

<body>

    <div id="wrapper">

        <div class="container">

            <section id="top" class="section docs-heading">

                <div class="row">
                    <div class="col-md-12">
                        <div class="big-title text-center">
                            <h1>Process Scheduling Algorithms</h1>
                        </div>
                        <!-- end title -->
                    </div>
                    <!-- end 12 -->
                </div>
                <!-- end row -->

                <hr>

            </section>
            <!-- end section -->

            <div class="row">

                <div class="col-md-3">
                    <nav class="docs-sidebar" data-spy="affix" data-offset-top="300" data-offset-bottom="200" role="navigation">
                        <ul class="nav">
                            <li><a href="#line1">Introduction</a>
                              <ul class="nav">
                                  <li><a href="#line1_1">CPU-I/O Burst Cycle</a></li>
                                  <li><a href="#line1_2">CPU Scheduler</a></li>
                                  <li><a href="#line1_3">Dispatcher</a></li>
                              </ul>
                            </li>
                            <li><a href="#line2">FCFS</a>
                              <ul class="nav">
                                  <li><a href="#line2_1">Description</a></li>
                                  <li><a href="#line2_2">Demerits</a></li>
                                  <!-- <li><a href="#line2_3">Example</a></li> -->
                              </ul>
                            </li>
                            <li><a href="#line3">SJF</a>
                              <ul class="nav">
                                  <li><a href="#line3_1">Description</a></li>
                                  <li><a href="#line3_2">Demerits</a></li>
                                  <!-- <li><a href="#line3_3">Example</a></li> -->
                              </ul>
                            </li>
                            <li><a href="#line4">SRTF</a>
                              <ul class="nav">
                                  <li><a href="#line4_1">Description</a></li>
                                  <!-- <li><a href="#line4_2">Example</a></li> -->
                              </ul>
                            </li>
                            <li><a href="#line5">NPPS</a>
                              <ul class="nav">
                                  <li><a href="#line5_1">Description</a></li>
                                  <li><a href="#line5_2">Demerits</a></li>
                                  <!-- <li><a href="#line5_3">Example</a></li> -->
                              </ul>
                            </li>
                            <li><a href="#line6">PPS</a>
                              <ul class="nav">
                                  <li><a href="#line6_1">Description</a></li>
                                  <!-- <li><a href="#line6_2">Example</a></li> -->
                              </ul>
                            </li>
                            <li><a href="#line7">RR</a>
                              <ul class="nav">
                                  <li><a href="#line7_1">Description</a></li>
                                  <li><a href="#line7_2">Performance</a></li>
                                  <!-- <li><a href="#line7_3">Example</a></li> -->
                              </ul>
                            </li>
                            <li><a href="#line8">MQWF</a>
                              <ul class="nav">
                                  <li><a href="#line8_1">Description</a></li>
                                  <li><a href="#line8_2">Merits</a></li>
                                  <li><a href="#line8_3">Demerits</a></li>
                                  <!-- <li><a href="#line8_4">Example</a></li> -->
                              </ul>
                            </li>
                        </ul>
                    </nav >
                </div>
                <div class="col-md-9">
                    <section id = "line1" class="welcome">

                        <div class="row">
                            <div class="col-md-12 left-align">
                                <h2 class="dark-text">Introduction<hr></h2>
                                <div class="row">

                                    <div class="col-md-12 full">
                                        <div class="intro1">
                                            <ul>
                                                <!-- <li><strong>Demo Page : </strong><a href="http://themeforest.net/user/surjithctly" target="_blank">Click Here</a></li> -->
                                                <li><strong>Front End Developers : </strong>Arvind Sai K, Kaushik S Kalmady</li>
                                                <li><strong>Backend End Developers : </strong>Aneesh Aithal, Derik Clive, Puneet U, Karthik M, Kaushik S Kalmady</li>
                                                <li><strong>Server Side Integration : </strong>Kaushik S Kalmady</li>
                                                <li><strong>Content : </strong>Karthik M</li>
                                            </ul>
                                        </div>

                                        <hr>
                                        <div>
                                            <p>CPU scheduling is a process which allows one process to use the CPU while the execution of another process is on hold (in waiting state) due to unavailability of any resource like I/O etc., thereby making full use of CPU. The aim of CPU scheduling is to make the system efficient, fast and fair.
                                            </p>
                                            <h4 >Basic Concepts</h4>
                                            <h5 id = "line1_1">CPU-I/O Burst Cycle</h5>
                                            <p>Process execution consists of a cycle of CPU execution and I/O wait. Processes alternate between these two states. Process execution begins with a CPU burst. That is followed by an I/O burst, which is followed by another CPU burst, then another I/O burst, and so on. Eventually, the final CPU burst ends with a system request to terminate execution.
                                            </p>
                                            <h5 id = "line1_2">CPU Scheduler</h5>
                                            <p>Whenever the CPU becomes idle, the operating system must select one of the processes in the ready queue to be executed. The selection process is carried out by the short-term scheduler, or CPU scheduler. The scheduler selects a process from the processes in memory that are ready to execute and allocates the CPU to that process.
                                            </p>
                                            <h5 id = "line1_3">Dispatcher</h5>
                                            <p>The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This function involves the following:
                                            </p>
                                            <ul>
                                              <li>Switching context</li>
                                              <li>Switching to user mode</li>
                                              <li>Jumping to the proper location in the user program to restart that program</li>
                                            </ul>
                                        </div>
                                    </div>
                                </div>
                                <!-- end row -->
                            </div>
                        </div>
                    <hr>
                    </section>

                    <section id="line2" class="section">

                        <div class="row">
                            <div class="col-md-12 left-align">
                                <h2 class="dark-text">First Come First Serve<a href="#top">#back to top</a><hr></h2>
                            </div>
                            <!-- end col -->
                        </div>
                        <!-- end row -->

                        <div class="row">
                                <h4 id="line2_1">Description</h4>
                                <p>The simplest of all scheduling algorithms. The process that requested the CPU first is allocated the CPU first</p>
                                  <!-- end col -->
                        </div>
                        <!-- end row -->

                        <hr>
                        <div class="row">
                                <h4 id="line2_2">Demerits</h4>
                                <ol>
                                  <li>Average waiting time under FCFS policy is quite long</li>
                                  <li>A smaller process has to wait for a large amount of time before a bigger process that has been allocated CPU finishes its execution</li>
                                  <li>Not suitable for time sharing systems where each user gets a share of CPU at regular intervals</li>
                                </ol>
                            <!-- end col -->
                        </div>
                        <hr>

                        <!-- <div class = "row">
                          <h4 id ="line2_3">Example</h4>
                        </div>
                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Input</h4>
                        </div>

                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Output</h4>
                        </div> -->


                    </section>
                    <!-- end section -->

                    <section id="line3" class="section">

                        <div class="row">
                            <div class="col-md-12 left-align">
                                <h2 class="dark-text">Shortest Job First Scheduling<a href="#top">#back to top</a><hr></h2>
                            </div>
                            <!-- end col -->
                        </div>
                        <!-- end row -->

                        <div class="row">
                                <h4 id="line3_1">Description</h4>
                                <p>The scheduling criteria under this policy depends on which process has the shortest-next-CPU-burst. It is an optimal way of CPU scheduling, i.e it gives the minimum average waiting time for a set of processes. If two process have the same burst time left, FCFS is used to resolve the tie</p>  <!-- end col -->
                        </div>
                        <!-- end row -->

                        <hr>
                        <div class="row">
                                <h4 id="line3_2">Demerits</h4>
                                <ol>
                                  <li>It often cannot be implemented at the level of short-term CPU scheduling as there is no way to know the length of the next CPU burst</li>
                                  <li>The next CPU burst length is thereby approximated using statistical techniques like exponential average</li>
                                </ol>
                            <!-- end col -->
                        </div>
                        <hr>

                        <!-- <div class = "row">
                          <h4 id ="line3_3">Example</h4>
                        </div>
                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Input</h4>
                        </div>

                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Output</h4>
                        </div> -->


                    </section>
                    <!-- end section -->
                    <section id="line4" class="section">

                        <div class="row">
                            <div class="col-md-12 left-align">
                                <h2 class="dark-text">Shortest Remaining Time First<a href="#top">#back to top</a><hr></h2>
                            </div>
                            <!-- end col -->
                        </div>
                        <!-- end row -->

                        <div class="row">
                                <h4 id="line4_1">Description</h4>
                                <p>This is the preemptive version of Shortest Job First scheduling. A newly arrived process in the ready queue may have a burst time lesser than that of the current process getting executed. In such a case, the current process is preempted and the newly arrived process is scheduled to execute. Similar to SJF, FCFS is used to resolve the tie here.</p>
                      </div>
                        <!-- end row -->

                        <hr>


                        <!-- <div class = "row">
                          <h4 id ="line4_2">Example</h4>
                        </div>
                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Input</h4>
                        </div>

                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Output</h4>
                        </div> -->


                    </section>
                    <section id="line5" class="section">

                        <div class="row">
                            <div class="col-md-12 left-align">
                                <h2 class="dark-text">Non-Preemptive Priority Scheduling<a href="#top">#back to top</a><hr></h2>
                            </div>
                            <!-- end col -->
                        </div>
                        <!-- end row -->

                        <div class="row">
                                <h4 id="line5_1">Description</h4>
                                <p>A more general case of the SJF scheduling where the priority was based on burst time. Each process is associated with a priority and CPU is allocated to the process with highest priority. Equal priority processes are scheduled in FCFS order. A newly arrived process is simply put in the ready queue based on its priority and does not interrupt the currently executing process.</p>
                        </div>
                        <!-- end row -->

                        <hr>

                        <div class="row">
                          <h4 id="line5_2">Demerits</h4>
                          <ol>
                            <li>In a heavily loaded computer system, a steady stream of high priority processes can leave some low priority processes waiting for a long time. This is called as indefinite blocking or starvation</li>
                            <li>A solution to the problem of indefinite blocking is called aging, where priorities of processes that wait in the system for a long time are increased</li>
                          </ol>
                          <!-- end col -->
                        </div>

                        <!-- <div class = "row">
                          <h4 id ="line5_3">Example</h4>
                        </div>
                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Input</h4>
                        </div>

                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Output</h4>
                        </div> -->


                    </section>

                    <section id="line6" class="section">

                        <div class="row">
                            <div class="col-md-12 left-align">
                                <h2 class="dark-text">Preemptive Priority Scheduling<a href="#top">#back to top</a><hr></h2>
                            </div>
                            <!-- end col -->
                        </div>
                        <!-- end row -->

                        <div class="row">
                                <h4 id="line6_1">Description</h4>
                              <p>It is a preemptive version of the priority scheduling algorithm. The priority of newly arrived processes are compared with the currently executing process. If the priority is higher, then the currently executing process is preempted and the newly arrived process executes</p>
                        </div>
                        <!-- end row -->

                        <hr>

                        <!-- <div class = "row">
                          <h4 id ="line6_2">Example</h4>
                        </div>
                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Input</h4>
                        </div>

                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Output</h4>
                        </div> -->


                    </section>
                    <section id="line7" class="section">

                        <div class="row">
                            <div class="col-md-12 left-align">
                                <h2 class="dark-text">Round Robin Scheduling<a href="#top">#back to top</a><hr></h2>
                            </div>
                            <!-- end col -->
                        </div>
                        <!-- end row -->

                        <div class="row">
                                <h4 id="line7_1">Description</h4>
                                <p>The ready queue is treated as a circular queue. The CPU scheduler goes around the queue, allocating the CPU to each of the processes a time period of 1 quantum.
If the burst time left for a process is less than the time quantum, then the process will itself release the CPU voluntarily.
If the burst time left is more than 1 time quantum, the timer for that process will go off and a context switch is forced.
This algorithm is preemptive by its nature.</p>
                        </div>
                        <!-- end row -->

                        <hr>

                        <div class="row">
                          <h4 id="line7_2">Performance</h4>
                          <ol>
                            <li>Performance depends heavily on the time quantum. A very large time quantum will it make it effectively an FCFS algorithms and a very short time quantum will force a very large number of context switches</li>
                            <li>A rule of thumb is that 80% of the CPU bursts must be shorter than the time quantum</li>
                          </ol>
                          <!-- end col -->
                        </div>

                        <!-- <div class = "row">
                          <h4 id ="line7_3">Example</h4>
                        </div>
                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Input</h4>
                        </div>

                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Output</h4>
                        </div> -->


                    </section>
                    <section id="line8" class="section">

                        <div class="row">
                            <div class="col-md-12 left-align">
                                <h2 class="dark-text">Multilevel Queue Scheduling Without Feedback<a href="#top">#back to top</a><hr></h2>
                            </div>
                            <!-- end col -->
                        </div>
                        <!-- end row -->

                        <div class="row">
                                <h4 id="line8_1">Description</h4>
                                <p>Different types of processes have different response time requirements and so may have different scheduling needs. A multilevel queue scheduling partitions the ready queue into two separate queues, one for foreground processes and the other for background processes. The foreground queue is scheduled with round robin algorithm and the background queue using FCFS. There is also fixed-priority preemptive scheduling among the queues themselves. The foreground queue has absolute priority over the background queue. No process in the background queue can run unless until the foreground is empty.</p>
                        </div>
                        <!-- end row -->

                        <hr>

                        <div class="row">
                          <h4 id="line8_2">Merits</h4>
                          <ol>
                            <li>Processes are permanently assigned to the queues when they enter the system. Processes do not move from one queue to another since processes do not change their foreground or background nature. This setup has the advantage of low scheduling overhead. </li>
                          </ol>
                          <!-- end col -->
                        </div>


                        <div class="row">
                          <h4 id="line8_3">Demerits</h4>
                          <ol>
                            <li>Processes in the low priority queue may wait indefinitely if there are high priority processes generated continually by the system leading to indefinite starvation. This is corrected in the multilevel feedback queue scheduling where high priority processes that use too much CPU time will be pushed down to lower priority queues and low priority processes which have been waiting for long are pushed up the priority queues</li>
                          </ol>
                          <!-- end col -->
                        </div>

                        <!-- <div class = "row">
                          <h4 id ="line8_4">Example</h4>
                        </div>
                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Input</h4>
                        </div>

                        <div class="col-md-6">
                            <a href="upload/thumbnail.png" data-rel="prettyPhoto"><img src="images/upload/thumbnail.png" alt="" class="img-responsive img-thumbnail"></a>
                            <h4>Output</h4>
                        </div> -->


                    </section>
                </div>
                <!-- // end .col -->

            </div>
            <!-- // end .row -->

        </div>
        <!-- // end container -->

    </div>
    <!-- end wrapper -->

    <script src="{%static 'wikipages/js/jquery.min.js' %}"></script>
    <script src="{%static 'wikipages/js/bootstrap.min.js' %}"></script>
    <script src="{%static 'wikipages/js/retina.js' %}"></script>
    <script src="{%static 'wikipages/js/jquery.fitvids.js' %}"></script>
    <script src="{%static 'wikipages/js/wow.js' %}"></script>
    <script src="{%static 'wikipages/js/jquery.prettyPhoto.js' %}"></script>
    <script src="{%static 'wikipages/js/custom.js' %}"></script>
    <script src="{%static 'wikipages/js/main.js' %}"></script>
    <script src="{%static 'wikipages/js/syntax-highlighter/scripts/shCore.js' %}"></script>
    <script src="{%static 'wikipages/js/syntax-highlighter/scripts/shBrushXml.js' %}"></script>
    <script src="{%static 'wikipages/js/syntax-highlighter/scripts/shBrushCss.js' %}"></script>
    <script src="{%static 'wikipages/js/syntax-highlighter/scripts/shBrushJScript.js' %}"></script>

</body>

</html>
